|
In combinatorial mathematics, a Baxter permutation is a permutation which satisfies the following generalized pattern avoidance property: * There are no indices ''i'' < ''j'' < ''k'' such that ''σ''(''j'' + 1) < ''σ''(''i'') < ''σ''(''k'') < ''σ''(''j'') or ''σ''(''j'') < ''σ''(''k'') < ''σ''(''i'') < ''σ''(''j'' + 1). For example, the permutation ''σ'' = 2413 in ''S''4 (written in one-line notation) is ''not'' a Baxter permutation because, taking ''i'' = 1, ''j'' = 2 and ''k'' = 4, this permutation violates the first condition. These permutations were introduced by Glen E. Baxter in the context of mathematical analysis. == Enumeration == For ''n'' = 1, 2, 3, ..., the number ''an'' of Baxter permutations of length ''n'' is 1, 2, 6, 22, 92, 422, 2074, 10754, 58202, 326240, 1882960, 11140560, 67329992, 414499438, 2593341586, 16458756586,... This is sequence in the OEIS. In general, ''a''''n'' has the following formula: ::〔.〕 In fact, this formula is graded by the number of descents in the permutations, i.e., there are Baxter permutations in ''S''''n'' with ''k-1'' descents. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Baxter permutation」の詳細全文を読む スポンサード リンク
|